home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / test / test_random.py < prev    next >
Text File  |  2005-10-18  |  20KB  |  518 lines
  1. #!/usr/bin/env python
  2.  
  3. import unittest
  4. import random
  5. import time
  6. import pickle
  7. import warnings
  8. from math import log, exp, sqrt, pi
  9. from test import test_support
  10.  
  11. class TestBasicOps(unittest.TestCase):
  12.     # Superclass with tests common to all generators.
  13.     # Subclasses must arrange for self.gen to retrieve the Random instance
  14.     # to be tested.
  15.  
  16.     def randomlist(self, n):
  17.         """Helper function to make a list of random numbers"""
  18.         return [self.gen.random() for i in xrange(n)]
  19.  
  20.     def test_autoseed(self):
  21.         self.gen.seed()
  22.         state1 = self.gen.getstate()
  23.         time.sleep(0.1)
  24.         self.gen.seed()      # diffent seeds at different times
  25.         state2 = self.gen.getstate()
  26.         self.assertNotEqual(state1, state2)
  27.  
  28.     def test_saverestore(self):
  29.         N = 1000
  30.         self.gen.seed()
  31.         state = self.gen.getstate()
  32.         randseq = self.randomlist(N)
  33.         self.gen.setstate(state)    # should regenerate the same sequence
  34.         self.assertEqual(randseq, self.randomlist(N))
  35.  
  36.     def test_seedargs(self):
  37.         for arg in [None, 0, 0L, 1, 1L, -1, -1L, 10**20, -(10**20),
  38.                     3.14, 1+2j, 'a', tuple('abc')]:
  39.             self.gen.seed(arg)
  40.         for arg in [range(3), dict(one=1)]:
  41.             self.assertRaises(TypeError, self.gen.seed, arg)
  42.         self.assertRaises(TypeError, self.gen.seed, 1, 2)
  43.         self.assertRaises(TypeError, type(self.gen), [])
  44.  
  45.     def test_jumpahead(self):
  46.         self.gen.seed()
  47.         state1 = self.gen.getstate()
  48.         self.gen.jumpahead(100)
  49.         state2 = self.gen.getstate()    # s/b distinct from state1
  50.         self.assertNotEqual(state1, state2)
  51.         self.gen.jumpahead(100)
  52.         state3 = self.gen.getstate()    # s/b distinct from state2
  53.         self.assertNotEqual(state2, state3)
  54.  
  55.         self.assertRaises(TypeError, self.gen.jumpahead)  # needs an arg
  56.         self.assertRaises(TypeError, self.gen.jumpahead, "ick")  # wrong type
  57.         self.assertRaises(TypeError, self.gen.jumpahead, 2.3)  # wrong type
  58.         self.assertRaises(TypeError, self.gen.jumpahead, 2, 3)  # too many
  59.  
  60.     def test_sample(self):
  61.         # For the entire allowable range of 0 <= k <= N, validate that
  62.         # the sample is of the correct length and contains only unique items
  63.         N = 100
  64.         population = xrange(N)
  65.         for k in xrange(N+1):
  66.             s = self.gen.sample(population, k)
  67.             self.assertEqual(len(s), k)
  68.             uniq = set(s)
  69.             self.assertEqual(len(uniq), k)
  70.             self.failUnless(uniq <= set(population))
  71.         self.assertEqual(self.gen.sample([], 0), [])  # test edge case N==k==0
  72.  
  73.     def test_sample_distribution(self):
  74.         # For the entire allowable range of 0 <= k <= N, validate that
  75.         # sample generates all possible permutations
  76.         n = 5
  77.         pop = range(n)
  78.         trials = 10000  # large num prevents false negatives without slowing normal case
  79.         def factorial(n):
  80.             return reduce(int.__mul__, xrange(1, n), 1)
  81.         for k in xrange(n):
  82.             expected = factorial(n) // factorial(n-k)
  83.             perms = {}
  84.             for i in xrange(trials):
  85.                 perms[tuple(self.gen.sample(pop, k))] = None
  86.                 if len(perms) == expected:
  87.                     break
  88.             else:
  89.                 self.fail()
  90.  
  91.     def test_sample_inputs(self):
  92.         # SF bug #801342 -- population can be any iterable defining __len__()
  93.         self.gen.sample(set(range(20)), 2)
  94.         self.gen.sample(range(20), 2)
  95.         self.gen.sample(xrange(20), 2)
  96.         self.gen.sample(dict.fromkeys('abcdefghijklmnopqrst'), 2)
  97.         self.gen.sample(str('abcdefghijklmnopqrst'), 2)
  98.         self.gen.sample(tuple('abcdefghijklmnopqrst'), 2)
  99.  
  100.     def test_gauss(self):
  101.         # Ensure that the seed() method initializes all the hidden state.  In
  102.         # particular, through 2.2.1 it failed to reset a piece of state used
  103.         # by (and only by) the .gauss() method.
  104.  
  105.         for seed in 1, 12, 123, 1234, 12345, 123456, 654321:
  106.             self.gen.seed(seed)
  107.             x1 = self.gen.random()
  108.             y1 = self.gen.gauss(0, 1)
  109.  
  110.             self.gen.seed(seed)
  111.             x2 = self.gen.random()
  112.             y2 = self.gen.gauss(0, 1)
  113.  
  114.             self.assertEqual(x1, x2)
  115.             self.assertEqual(y1, y2)
  116.  
  117.     def test_pickling(self):
  118.         state = pickle.dumps(self.gen)
  119.         origseq = [self.gen.random() for i in xrange(10)]
  120.         newgen = pickle.loads(state)
  121.         restoredseq = [newgen.random() for i in xrange(10)]
  122.         self.assertEqual(origseq, restoredseq)
  123.  
  124. class WichmannHill_TestBasicOps(TestBasicOps):
  125.     gen = random.WichmannHill()
  126.  
  127.     def test_setstate_first_arg(self):
  128.         self.assertRaises(ValueError, self.gen.setstate, (2, None, None))
  129.  
  130.     def test_strong_jumpahead(self):
  131.         # tests that jumpahead(n) semantics correspond to n calls to random()
  132.         N = 1000
  133.         s = self.gen.getstate()
  134.         self.gen.jumpahead(N)
  135.         r1 = self.gen.random()
  136.         # now do it the slow way
  137.         self.gen.setstate(s)
  138.         for i in xrange(N):
  139.             self.gen.random()
  140.         r2 = self.gen.random()
  141.         self.assertEqual(r1, r2)
  142.  
  143.     def test_gauss_with_whseed(self):
  144.         # Ensure that the seed() method initializes all the hidden state.  In
  145.         # particular, through 2.2.1 it failed to reset a piece of state used
  146.         # by (and only by) the .gauss() method.
  147.  
  148.         for seed in 1, 12, 123, 1234, 12345, 123456, 654321:
  149.             self.gen.whseed(seed)
  150.             x1 = self.gen.random()
  151.             y1 = self.gen.gauss(0, 1)
  152.  
  153.             self.gen.whseed(seed)
  154.             x2 = self.gen.random()
  155.             y2 = self.gen.gauss(0, 1)
  156.  
  157.             self.assertEqual(x1, x2)
  158.             self.assertEqual(y1, y2)
  159.  
  160.     def test_bigrand(self):
  161.         # Verify warnings are raised when randrange is too large for random()
  162.         oldfilters = warnings.filters[:]
  163.         warnings.filterwarnings("error", "Underlying random")
  164.         self.assertRaises(UserWarning, self.gen.randrange, 2**60)
  165.         warnings.filters[:] = oldfilters
  166.  
  167. class SystemRandom_TestBasicOps(TestBasicOps):
  168.     gen = random.SystemRandom()
  169.  
  170.     def test_autoseed(self):
  171.         # Doesn't need to do anything except not fail
  172.         self.gen.seed()
  173.  
  174.     def test_saverestore(self):
  175.         self.assertRaises(NotImplementedError, self.gen.getstate)
  176.         self.assertRaises(NotImplementedError, self.gen.setstate, None)
  177.  
  178.     def test_seedargs(self):
  179.         # Doesn't need to do anything except not fail
  180.         self.gen.seed(100)
  181.  
  182.     def test_jumpahead(self):
  183.         # Doesn't need to do anything except not fail
  184.         self.gen.jumpahead(100)
  185.  
  186.     def test_gauss(self):
  187.         self.gen.gauss_next = None
  188.         self.gen.seed(100)
  189.         self.assertEqual(self.gen.gauss_next, None)
  190.  
  191.     def test_pickling(self):
  192.         self.assertRaises(NotImplementedError, pickle.dumps, self.gen)
  193.  
  194.     def test_53_bits_per_float(self):
  195.         # This should pass whenever a C double has 53 bit precision.
  196.         span = 2 ** 53
  197.         cum = 0
  198.         for i in xrange(100):
  199.             cum |= int(self.gen.random() * span)
  200.         self.assertEqual(cum, span-1)
  201.  
  202.     def test_bigrand(self):
  203.         # The randrange routine should build-up the required number of bits
  204.         # in stages so that all bit positions are active.
  205.         span = 2 ** 500
  206.         cum = 0
  207.         for i in xrange(100):
  208.             r = self.gen.randrange(span)
  209.             self.assert_(0 <= r < span)
  210.             cum |= r
  211.         self.assertEqual(cum, span-1)
  212.  
  213.     def test_bigrand_ranges(self):
  214.         for i in [40,80, 160, 200, 211, 250, 375, 512, 550]:
  215.             start = self.gen.randrange(2 ** i)
  216.             stop = self.gen.randrange(2 ** (i-2))
  217.             if stop <= start:
  218.                 return
  219.             self.assert_(start <= self.gen.randrange(start, stop) < stop)
  220.  
  221.     def test_rangelimits(self):
  222.         for start, stop in [(-2,0), (-(2**60)-2,-(2**60)), (2**60,2**60+2)]:
  223.             self.assertEqual(set(range(start,stop)),
  224.                 set([self.gen.randrange(start,stop) for i in xrange(100)]))
  225.  
  226.     def test_genrandbits(self):
  227.         # Verify ranges
  228.         for k in xrange(1, 1000):
  229.             self.assert_(0 <= self.gen.getrandbits(k) < 2**k)
  230.  
  231.         # Verify all bits active
  232.         getbits = self.gen.getrandbits
  233.         for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
  234.             cum = 0
  235.             for i in xrange(100):
  236.                 cum |= getbits(span)
  237.             self.assertEqual(cum, 2**span-1)
  238.  
  239.         # Verify argument checking
  240.         self.assertRaises(TypeError, self.gen.getrandbits)
  241.         self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
  242.         self.assertRaises(ValueError, self.gen.getrandbits, 0)
  243.         self.assertRaises(ValueError, self.gen.getrandbits, -1)
  244.         self.assertRaises(TypeError, self.gen.getrandbits, 10.1)
  245.  
  246.     def test_randbelow_logic(self, _log=log, int=int):
  247.         # check bitcount transition points:  2**i and 2**(i+1)-1
  248.         # show that: k = int(1.001 + _log(n, 2))
  249.         # is equal to or one greater than the number of bits in n
  250.         for i in xrange(1, 1000):
  251.             n = 1L << i # check an exact power of two
  252.             numbits = i+1
  253.             k = int(1.00001 + _log(n, 2))
  254.             self.assertEqual(k, numbits)
  255.             self.assert_(n == 2**(k-1))
  256.  
  257.             n += n - 1      # check 1 below the next power of two
  258.             k = int(1.00001 + _log(n, 2))
  259.             self.assert_(k in [numbits, numbits+1])
  260.             self.assert_(2**k > n > 2**(k-2))
  261.  
  262.             n -= n >> 15     # check a little farther below the next power of two
  263.             k = int(1.00001 + _log(n, 2))
  264.             self.assertEqual(k, numbits)        # note the stronger assertion
  265.             self.assert_(2**k > n > 2**(k-1))   # note the stronger assertion
  266.  
  267.  
  268. class MersenneTwister_TestBasicOps(TestBasicOps):
  269.     gen = random.Random()
  270.  
  271.     def test_setstate_first_arg(self):
  272.         self.assertRaises(ValueError, self.gen.setstate, (1, None, None))
  273.  
  274.     def test_setstate_middle_arg(self):
  275.         # Wrong type, s/b tuple
  276.         self.assertRaises(TypeError, self.gen.setstate, (2, None, None))
  277.         # Wrong length, s/b 625
  278.         self.assertRaises(ValueError, self.gen.setstate, (2, (1,2,3), None))
  279.         # Wrong type, s/b tuple of 625 ints
  280.         self.assertRaises(TypeError, self.gen.setstate, (2, ('a',)*625, None))
  281.         # Last element s/b an int also
  282.         self.assertRaises(TypeError, self.gen.setstate, (2, (0,)*624+('a',), None))
  283.  
  284.     def test_referenceImplementation(self):
  285.         # Compare the python implementation with results from the original
  286.         # code.  Create 2000 53-bit precision random floats.  Compare only
  287.         # the last ten entries to show that the independent implementations
  288.         # are tracking.  Here is the main() function needed to create the
  289.         # list of expected random numbers:
  290.         #    void main(void){
  291.         #         int i;
  292.         #         unsigned long init[4]={61731, 24903, 614, 42143}, length=4;
  293.         #         init_by_array(init, length);
  294.         #         for (i=0; i<2000; i++) {
  295.         #           printf("%.15f ", genrand_res53());
  296.         #           if (i%5==4) printf("\n");
  297.         #         }
  298.         #     }
  299.         expected = [0.45839803073713259,
  300.                     0.86057815201978782,
  301.                     0.92848331726782152,
  302.                     0.35932681119782461,
  303.                     0.081823493762449573,
  304.                     0.14332226470169329,
  305.                     0.084297823823520024,
  306.                     0.53814864671831453,
  307.                     0.089215024911993401,
  308.                     0.78486196105372907]
  309.  
  310.         self.gen.seed(61731L + (24903L<<32) + (614L<<64) + (42143L<<96))
  311.         actual = self.randomlist(2000)[-10:]
  312.         for a, e in zip(actual, expected):
  313.             self.assertAlmostEqual(a,e,places=14)
  314.  
  315.     def test_strong_reference_implementation(self):
  316.         # Like test_referenceImplementation, but checks for exact bit-level
  317.         # equality.  This should pass on any box where C double contains
  318.         # at least 53 bits of precision (the underlying algorithm suffers
  319.         # no rounding errors -- all results are exact).
  320.         from math import ldexp
  321.  
  322.         expected = [0x0eab3258d2231fL,
  323.                     0x1b89db315277a5L,
  324.                     0x1db622a5518016L,
  325.                     0x0b7f9af0d575bfL,
  326.                     0x029e4c4db82240L,
  327.                     0x04961892f5d673L,
  328.                     0x02b291598e4589L,
  329.                     0x11388382c15694L,
  330.                     0x02dad977c9e1feL,
  331.                     0x191d96d4d334c6L]
  332.         self.gen.seed(61731L + (24903L<<32) + (614L<<64) + (42143L<<96))
  333.         actual = self.randomlist(2000)[-10:]
  334.         for a, e in zip(actual, expected):
  335.             self.assertEqual(long(ldexp(a, 53)), e)
  336.  
  337.     def test_long_seed(self):
  338.         # This is most interesting to run in debug mode, just to make sure
  339.         # nothing blows up.  Under the covers, a dynamically resized array
  340.         # is allocated, consuming space proportional to the number of bits
  341.         # in the seed.  Unfortunately, that's a quadratic-time algorithm,
  342.         # so don't make this horribly big.
  343.         seed = (1L << (10000 * 8)) - 1  # about 10K bytes
  344.         self.gen.seed(seed)
  345.  
  346.     def test_53_bits_per_float(self):
  347.         # This should pass whenever a C double has 53 bit precision.
  348.         span = 2 ** 53
  349.         cum = 0
  350.         for i in xrange(100):
  351.             cum |= int(self.gen.random() * span)
  352.         self.assertEqual(cum, span-1)
  353.  
  354.     def test_bigrand(self):
  355.         # The randrange routine should build-up the required number of bits
  356.         # in stages so that all bit positions are active.
  357.         span = 2 ** 500
  358.         cum = 0
  359.         for i in xrange(100):
  360.             r = self.gen.randrange(span)
  361.             self.assert_(0 <= r < span)
  362.             cum |= r
  363.         self.assertEqual(cum, span-1)
  364.  
  365.     def test_bigrand_ranges(self):
  366.         for i in [40,80, 160, 200, 211, 250, 375, 512, 550]:
  367.             start = self.gen.randrange(2 ** i)
  368.             stop = self.gen.randrange(2 ** (i-2))
  369.             if stop <= start:
  370.                 return
  371.             self.assert_(start <= self.gen.randrange(start, stop) < stop)
  372.  
  373.     def test_rangelimits(self):
  374.         for start, stop in [(-2,0), (-(2**60)-2,-(2**60)), (2**60,2**60+2)]:
  375.             self.assertEqual(set(range(start,stop)),
  376.                 set([self.gen.randrange(start,stop) for i in xrange(100)]))
  377.  
  378.     def test_genrandbits(self):
  379.         # Verify cross-platform repeatability
  380.         self.gen.seed(1234567)
  381.         self.assertEqual(self.gen.getrandbits(100),
  382.                          97904845777343510404718956115L)
  383.         # Verify ranges
  384.         for k in xrange(1, 1000):
  385.             self.assert_(0 <= self.gen.getrandbits(k) < 2**k)
  386.  
  387.         # Verify all bits active
  388.         getbits = self.gen.getrandbits
  389.         for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
  390.             cum = 0
  391.             for i in xrange(100):
  392.                 cum |= getbits(span)
  393.             self.assertEqual(cum, 2**span-1)
  394.  
  395.         # Verify argument checking
  396.         self.assertRaises(TypeError, self.gen.getrandbits)
  397.         self.assertRaises(TypeError, self.gen.getrandbits, 'a')
  398.         self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
  399.         self.assertRaises(ValueError, self.gen.getrandbits, 0)
  400.         self.assertRaises(ValueError, self.gen.getrandbits, -1)
  401.  
  402.     def test_randbelow_logic(self, _log=log, int=int):
  403.         # check bitcount transition points:  2**i and 2**(i+1)-1
  404.         # show that: k = int(1.001 + _log(n, 2))
  405.         # is equal to or one greater than the number of bits in n
  406.         for i in xrange(1, 1000):
  407.             n = 1L << i # check an exact power of two
  408.             numbits = i+1
  409.             k = int(1.00001 + _log(n, 2))
  410.             self.assertEqual(k, numbits)
  411.             self.assert_(n == 2**(k-1))
  412.  
  413.             n += n - 1      # check 1 below the next power of two
  414.             k = int(1.00001 + _log(n, 2))
  415.             self.assert_(k in [numbits, numbits+1])
  416.             self.assert_(2**k > n > 2**(k-2))
  417.  
  418.             n -= n >> 15     # check a little farther below the next power of two
  419.             k = int(1.00001 + _log(n, 2))
  420.             self.assertEqual(k, numbits)        # note the stronger assertion
  421.             self.assert_(2**k > n > 2**(k-1))   # note the stronger assertion
  422.  
  423. _gammacoeff = (0.9999999999995183, 676.5203681218835, -1259.139216722289,
  424.               771.3234287757674,  -176.6150291498386, 12.50734324009056,
  425.               -0.1385710331296526, 0.9934937113930748e-05, 0.1659470187408462e-06)
  426.  
  427. def gamma(z, cof=_gammacoeff, g=7):
  428.     z -= 1.0
  429.     sum = cof[0]
  430.     for i in xrange(1,len(cof)):
  431.         sum += cof[i] / (z+i)
  432.     z += 0.5
  433.     return (z+g)**z / exp(z+g) * sqrt(2*pi) * sum
  434.  
  435. class TestDistributions(unittest.TestCase):
  436.     def test_zeroinputs(self):
  437.         # Verify that distributions can handle a series of zero inputs'
  438.         g = random.Random()
  439.         x = [g.random() for i in xrange(50)] + [0.0]*5
  440.         g.random = x[:].pop; g.uniform(1,10)
  441.         g.random = x[:].pop; g.paretovariate(1.0)
  442.         g.random = x[:].pop; g.expovariate(1.0)
  443.         g.random = x[:].pop; g.weibullvariate(1.0, 1.0)
  444.         g.random = x[:].pop; g.normalvariate(0.0, 1.0)
  445.         g.random = x[:].pop; g.gauss(0.0, 1.0)
  446.         g.random = x[:].pop; g.lognormvariate(0.0, 1.0)
  447.         g.random = x[:].pop; g.vonmisesvariate(0.0, 1.0)
  448.         g.random = x[:].pop; g.gammavariate(0.01, 1.0)
  449.         g.random = x[:].pop; g.gammavariate(1.0, 1.0)
  450.         g.random = x[:].pop; g.gammavariate(200.0, 1.0)
  451.         g.random = x[:].pop; g.betavariate(3.0, 3.0)
  452.  
  453.     def test_avg_std(self):
  454.         # Use integration to test distribution average and standard deviation.
  455.         # Only works for distributions which do not consume variates in pairs
  456.         g = random.Random()
  457.         N = 5000
  458.         x = [i/float(N) for i in xrange(1,N)]
  459.         for variate, args, mu, sigmasqrd in [
  460.                 (g.uniform, (1.0,10.0), (10.0+1.0)/2, (10.0-1.0)**2/12),
  461.                 (g.expovariate, (1.5,), 1/1.5, 1/1.5**2),
  462.                 (g.paretovariate, (5.0,), 5.0/(5.0-1),
  463.                                   5.0/((5.0-1)**2*(5.0-2))),
  464.                 (g.weibullvariate, (1.0, 3.0), gamma(1+1/3.0),
  465.                                   gamma(1+2/3.0)-gamma(1+1/3.0)**2) ]:
  466.             g.random = x[:].pop
  467.             y = []
  468.             for i in xrange(len(x)):
  469.                 try:
  470.                     y.append(variate(*args))
  471.                 except IndexError:
  472.                     pass
  473.             s1 = s2 = 0
  474.             for e in y:
  475.                 s1 += e
  476.                 s2 += (e - mu) ** 2
  477.             N = len(y)
  478.             self.assertAlmostEqual(s1/N, mu, 2)
  479.             self.assertAlmostEqual(s2/(N-1), sigmasqrd, 2)
  480.  
  481. class TestModule(unittest.TestCase):
  482.     def testMagicConstants(self):
  483.         self.assertAlmostEqual(random.NV_MAGICCONST, 1.71552776992141)
  484.         self.assertAlmostEqual(random.TWOPI, 6.28318530718)
  485.         self.assertAlmostEqual(random.LOG4, 1.38629436111989)
  486.         self.assertAlmostEqual(random.SG_MAGICCONST, 2.50407739677627)
  487.  
  488.     def test__all__(self):
  489.         # tests validity but not completeness of the __all__ list
  490.         self.failUnless(set(random.__all__) <= set(dir(random)))
  491.  
  492. def test_main(verbose=None):
  493.     testclasses =    [WichmannHill_TestBasicOps,
  494.                       MersenneTwister_TestBasicOps,
  495.                       TestDistributions,
  496.                       TestModule]
  497.  
  498.     try:
  499.         random.SystemRandom().random()
  500.     except NotImplementedError:
  501.         pass
  502.     else:
  503.         testclasses.append(SystemRandom_TestBasicOps)
  504.  
  505.     test_support.run_unittest(*testclasses)
  506.  
  507.     # verify reference counting
  508.     import sys
  509.     if verbose and hasattr(sys, "gettotalrefcount"):
  510.         counts = [None] * 5
  511.         for i in xrange(len(counts)):
  512.             test_support.run_unittest(*testclasses)
  513.             counts[i] = sys.gettotalrefcount()
  514.         print counts
  515.  
  516. if __name__ == "__main__":
  517.     test_main(verbose=True)
  518.